package 力扣;

/**
 * @author yyq
 * @create 2022-06-16 12:20
 */
public class leetcode96 {
    // 求n个节点的二叉搜索树的个数
    public int numTrees(int n) {
        if(n<=2) return n;
        int[] dp=new int[n+1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i=3;i<=n;i++){
            // 获得dp[i]
            int sum = 0;
            for (int j=1;j<=i;j++){
                sum = sum + dp[j-1]*dp[i-j];
            }
            dp[i]=sum;
        }
        return dp[n];
    }
}
